Packet classification is a function implemented in networking equipment such as routers and switches, that extracts information from an incoming packet (this is called parsing) and uses this to search a data base with rules. If a matching rule is found, then the processing of that packet will be based on data associated with that rule. The parsed information, the rules, and the way the rules are searched are dependent on the application.
For example, with an IP forwarding application, the packet classification consists of parsing the IP destination address from the IP header, which is then used to search a routing table according to a longest-matching prefix search. The routing table entry that results from this search provides the address of the next hop to which the packet will be forwarded. Another example is a firewall application, in which several fields (e.g., IP source and destination addresses, TCP port numbers, PROT byte) are parsed from the packet header, and are then used to search the highest-priority matching rule from a set of firewall rules. Data associated with this firewall rule will then indicate whether the packet will be permitted or denied access through the firewall.
Conventional applications, such as the two described examples, have in common that the information is parsed from well-known fields at fixed locations within the packet headers (up to layer 4), which have fixed and relatively small sizes (typically up to 32 bits). Furthermore, the classification can be performed in two distinct phases: First the information is parsed from the packet header. Next, the parsed information is used to search a data base.
Web-server load balancing, intrusion detection and virus scanning are examples of important emerging applications that require more advanced packet classification capabilities, than as required by “conventional” applications as described above. These more advanced capabilities relate specifically to the following aspects:    1) Besides information from the packet header, also information from the packet payload needs to be inspected.    2) The location and the amount of information that has to be inspected within the payload is not always known in advance and can for several applications only be determined during the classification operation. Some applications require the use of pattern-matching and regular-expression-based searches for locating information within the payload.    3) The amount of information involved in the packet classification can consist of up to multiple hundreds of bytes.
Examples of information that has to be inspected within the payload for a web-server load balancer application, are URLs, cookies, and SSL identifiers. Another example is a set of known character strings related to viruses that are checked for by a virus-scan application.
From the above it can be understood that the packet classification now becomes more complex in the following two respects:    1) The parsing operation becomes more difficult for applications in which the location and amount of information that needs to be parsed is not known in advance, and for applications for which a large amount of information needs to be parsed.    2) For certain applications the two distinct phases of parsing and searching cannot be used, but instead it is necessary to repeat parsing and searching in alternating steps or combine the two steps (e.g., pattern-matches).
In addition to the functional requirements outlined above, packet classification must be performed on the fly on incoming packets (this is called wire-speed packet classification) for typical link speeds between 1 Gb/sec and 10 Gb/sec today. A second requirement is that the data structures used for the packet classification should be organized such that a minimum amount of memory is needed for storing them, in order to minimize the costs. A third requirement is the support for fast updates of the rule set, as required by the dynamic nature of several new applications (e.g., web-server load balancing).
The standard solution for realizing a flexible parse function suitable for advanced packet classification as described above, is a programmable state machine. The concept and disadvantages of a prior-art implementation of a programmable state machine will now be illustrated using FIG. 1 and FIG. 2
FIG. 1 shows a state diagram for parsing two patterns “121h” (h means hexadecimal) and “ABh” from an input stream of 4-bit characters (input stream not shown). There are 6 possible states (S0, S1, S2, S3, S4, S5) represented by circles, the arrows (1; 2; A; B; 0, 2 . . . 9, B . . . F; 0, 2 . . . 9, C . . . F; 0, 3 . . . 9, B . . . F; and 0, 2 . . . 9, B . . . F) represent the state transitions. Nodes S3 and S5 are end states.
FIG. 2 shows a prior-art implementation of a programmable state machine for the state diagram of FIG. 1, which requires one memory access per state transition. In this example the states are assigned the following 3-bit state vectors:
S0 - 000bS1 - 001bS2 - 010bS3 - 011bS4 - 100bS5 - 101b
In FIG. 2 the current state (3 bits) concatenated with the 4-bit input value is used as an offset (address) into a table containing the next state for each possible combination of a current state and input value, resulting in a total of 2(3+4)=27=128 table entries. Disadvantages of this approach are (1) the inefficient use of storage (e.g., there are 128 table entries in FIG. 2 of which many contain the same next state) and (2) the large number of table entries that have to be written while “programming” the table for the given state diagram, resulting in a long construction (update) time.
In the U.S. patent of Solidum, U.S. Pat. No. 6,167,047, a programmable state machine is disclosed for packet classification. The Solidum patent approach requires at most one memory access per state transition, but requires less memory than the implementation concept shown in FIG. 2. A disadvantage of the Solidum approach is that it requires significantly more complex hardware: at least one processor, one program memory and one separate stack memory. This results in increased chip-area costs and increased power-consumption.
A prior-art solution for realizing a flexible search function suitable for advanced packet classification as described above, is a tree structure. One example is a Patricia tree as described in D. R. Morrison original paper “Patricia—Practical Algorithm to Retrieve Information Coded in Alphanumeric”, Journal of the ACM, Vol. 15, 1968.
A disadvantage of the prior-art is that no solutions exist that can support both efficient parsing and efficient searching. A programmable state machine cannot efficiently implement a search since the state space is typically too large, resulting in significant memory requirements and/or complex logic to determine the next state. On the other hand, a tree structure cannot implement parsing as efficiently as a programmable state machine, especially because the latter can more efficiently handle typical state transitions that are more complex than the branch functions which occur in a typical tree search. Therefore, implementing parsing using a tree structure, would require many nodes and therefore results in significant memory requirements.
Consequently, a disadvantage of the prior-art is that different hardware has to be used to implement the parsing and searching. A second disadvantage is that this makes it more difficult to realize a more advanced packet classification function, that supports the alternating use of parsing and searching or the combination of parsing and searching as described above.